package com.lfx.sort;

import java.util.Arrays;

/**
 * 快速排序法
 * @author 李逢喜
 * create 2021/7/16
 */
public class QuickSort1 {
    //双边循环法
    public static  void quickSort(int[] nums ,int startIndex ,int endIndex){
        if(startIndex>=endIndex)return;

        int povitPostion=getPovitPostion(nums,startIndex,endIndex);
        quickSort(nums,startIndex,povitPostion-1);
        quickSort(nums,povitPostion+1,endIndex);


    }


    /**
     * 获取基准元素下标
     * @param nums 排序数组
     * @param startIndex 开始下标
     * @param endIndex 结束下标
     * @return
     */
    public static  int getPovitPostion(int[] nums ,int startIndex ,int endIndex){
        int pivot=nums[startIndex];
        int left =startIndex;
        int right=endIndex;
        while (left!=right){
            while(left<right&nums[right]>pivot)
                right--;
            while(left<right&&nums[left]<=pivot)
                left++;

            if(left<right){
                int tmp=nums[right];
                nums[right]=nums[left];
                nums[left]=tmp;
            }
        }

        //pivot 和指针重合点交换
        nums[startIndex]=nums[left];
        nums[left]=pivot;

        return left;
    }


    public static void main(String[] args) {
        int[] nums={4,1,6,3,7,2,9,5,50,20};

        quickSort(nums,0,nums.length-1);
        System.out.println(Arrays.toString(nums));
    }


}
